package 题目集.动态规划.状压dp;

import java.util.Arrays;

import org.junit.Test;

/**
 * 我能赢吗 给定两个整数n和m 两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回） 抽取的整数会累加起来（两个玩家都算） 谁在自己的回合让累加和
 * >= m，谁获胜 若先出手的玩家能稳赢则返回true，否则返回false 假设两位玩家游戏时都绝顶聪明，可以全盘为自己打算 测试链接 :
 * https://leetcode.cn/problems/can-i-win/ 数据范围：1<=n<=20，m<=300
 */
public class ch01_我能赢吗 {
	public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
		n = maxChoosableInteger;
		sum = desiredTotal;
		if ((n + 1) * n / 2 < sum) {
			return false;
		}
		boolean res = dfs(sum, 0);
		return res;
	}

	// 这里dp表可以是一维的，因为sum是由path决定的。只有path是关键的
	byte[] dp = new byte[1 << 21];
	int n, sum;

	public boolean dfs(int sum, int path) {
		if (dp[path] != 0)
			return dp[path] == 1;
		if (sum <= 0) {
			dp[path] = 1;
			return true;
		}
		for (int i = n; i >= 1; i--) { // todo：为什么反过来不行
			int to = 1 << (i - 1);
			// 这个点没有被访问过，拿当前可以直接赢，或者对方无法赢
			if ((to & path) == 0 && (sum - i <= 0 || !dfs(sum - i, path | to))) {
				dp[path] = 1;
				return true;
			}
		}
		dp[path] = 2;
		return false;
	}

	@Test
	public void test() {
		int a = 18;
		int b = 79;
		System.out.println(canIWin(a, b));
	}
}
